/**
 * [52] N 皇后 II
 *
 * @format
 * @lc app=leetcode.cn id=52 lang=javascript
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function (n) {
    const memo = {
        cols: Array(n).fill(0),
        main: Array(2 * n - 1).fill(0),
        oppo: Array(2 * n - 1).fill(0)
    }
    let count = 0
    function setQueens(memo, n, i) {
        if (i === n - 1) {
            for (let j = 0; j < n; j++) {
                if (memo.cols[j] || memo.main[i - j + n - 1] || memo.oppo[i + j]) continue
                else count++
            }
        } else {
            for (let j = 0; j < n; j++) {
                if (memo.cols[j] || memo.main[i - j + n - 1] || memo.oppo[i + j]) continue
                else {
                    memo.cols[j] = 1
                    memo.main[i - j + n - 1] = 1
                    memo.oppo[i + j] = 1
                    setQueens(memo, n, i + 1)
                    memo.cols[j] = 0
                    memo.main[i - j + n - 1] = 0
                    memo.oppo[i + j] = 0
                }
            }
        }
        return count
    }
    setQueens(memo, n, 0)
    return count
}
// Accepted
// 9/9 cases passed (47 ms)
// Your runtime beats 99.62 % of javascript submissions
// Your memory usage beats 49.23 % of javascript submissions (49.9 MB)
// debugger
// console.log(totalNQueens(4))
// @lc code=end
